import heapq

class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        if not(nums1 and nums2): return []
        index = [0] * len(nums2)
        heap = [(nums1[index[i]] + nums2[i], i) for i in range(len(nums2))]
        heapq.heapify(heap)
        ret = []
        for _ in range(min(k, len(nums1)*len(nums2))):
            num, i = heapq.heappop(heap)
            ret.append([num-nums2[i], nums2[i]])
            index[i]+=1
            if index[i]>=len(nums1):
                continue
            else:
                heapq.heappush(heap, (nums1[index[i]]+nums2[i], i))
        return ret

print(Solution().kSmallestPairs([1,2,3,4,5,6], [3,5,7,9], 20))